class Solution
{
public:
    double frogPosition(int n, vector<vector<int>> &edges, int t, int target)
    {
        vector<double> probability(n + 1);
        probability[1] = 1.0;

        unordered_map<int, vector<int>> adjTable;
        for (auto &edge : edges)
        {
            adjTable[edge[0]].push_back(edge[1]);
            adjTable[edge[1]].push_back(edge[0]);
        }

        adjTable[1].push_back(1); // 统一根节点与非根节点的子节点数计算方式

        unordered_set<int> visited;
        queue<int> q;
        visited.insert(1);
        q.push(1);
        int time = 0;

        while (!q.empty())
        {
            if (time > t)
            {
                return 0.0;
            }

            int qSize = q.size();

            for (int _ = 0; _ < qSize; ++_)
            {
                int curPos = q.front();
                double curProbability = probability[curPos];
                q.pop();
                int childCount = adjTable[curPos].size() - 1;

                if (curPos == target)
                {
                    return (time == t || childCount == 0) ? curProbability : 0.0;
                }

                if (childCount == 0)
                {
                    continue;
                }

                for (int child : adjTable[curPos])
                {
                    if (!visited.count(child))
                    {
                        visited.insert(child);
                        q.push(child);
                        probability[child] = curProbability / childCount;
                    }
                }
            }
            ++time;
        }

        return 0.0;
    }
};